<?php
// +----------------------------------------------------------------------
// | 算法一: 分治法 ( Divide And Conquer )
// | 基本思想：
// |   将一个难以直接解决的大问题，分解成一些规模较小的相同问题，以便各个击破，分而治之。
// | 步骤：
// |   1）分解。将原问题分解成一系列子问题。
// |   2）求解。递归的求解各个子问题。若子问题足够小，则直接求解。
// |   3）合并。将子问题的解合并成原问题的解。
// | 典型实例：
// |   1）归并排序      O(nlogn)
// |   2）二分查找
// |   3）最大子段和问题 O(nlogn)
// +----------------------------------------------------------------------

namespace helper\algorithm;

class DivideAndConquer
{
    /**
     * 算法：使用代码实现对应的数学模型，从而解决对应的业务问题。
     * 编程思想：如何利用数学模式，来解决对应的需求问题；然后利用代码实现对应的数据模型（逻辑）。
     * 1、递归思想
     * 递归：指子程序（或函数）直接调用自己或通过一系列调用语句简介调用自己
     * 基本要素：
     *  1）边界条件，确定递归到何时终止，也称为递归出口
     *  2）递归模式，问题如何分解为小问题，也称为递归体
     * 注意：如果一个函数递归调用自己而没有递归出口，就是死循环
     * 应用：创建级联目录、删除目录、无限极分类等。
     *
     * 代码模式：
     * function  f1($n) {
     *    if($n == 最小级) {
     *        return  已知的值；
     *    }
     *    $result = 对 f1($n-1) 进行一个简单计算；
     *    return $result;
     * }
     *
     * 2、递推思想(迭代思想)
     * 递推: 即通过已知条件，利用特定关系得出中间推论，直至得到结果的算法。主要使用循环
     * 递推算法分为顺推和逆推两种。
     *  1) 顺推：通过最简单的条件（已知），然后逐步推演结果
     *  2) 逆推：通过结果找到规律，然后推到已知条件
     *
     * 代码模式：
     * $n = 已知的值； //通常就是指最小级的数据值，是已知的；
     * for ($i = 最小级的下一级， $i <= 目标级数； ++$i){
     *    $result = 对 $n 进行一个简单计算；
     *    $n = $result; //将当前求得的结果值，当做“要求的下一级的”前一个值；
     * }
     * 最后$result 就是结果；
     * 使用递归算法，到求第100个斐波那契数时会卡到机器跑不动，而使用递推算法，几乎不费时间。
     */

    public function demo()
    {
        $array = [-2, 11, -4, 13, -5, -2];
        // {11,-4, 13} 11-4+13=20
        $res = $this->maxSubSum($array, 0, 5);
        print_r($res);
    }

    /**
     * 最大子段和问题
     * 给定由n个整数（可能有负数）组成的序列，求序列子段和的最大值。当序列中所有整数均为负数时，其最大子段和为0。
     * @param array $array 数组
     * @param int $left  数组下标
     * @param int $right 数组下标
     * @return int|mixed
     */
    public function maxSubSum(array $array, int $left, int $right)
    {
        //$sum = 0;
        // 分解到单个整数，不可继续分解
        if ($left == $right) {
            if ($array[$left] > 0) {
                $sum = $array[$left];
            } else {
                $sum = 0;
            }
        } else {
            // 从left，right中间分解数组
            $center = intval(($left + $right) / 2);
            // 划分的位置
            $leftSum = $this->maxSubSum($array, $left, $center);
            $rightSum = $this->maxSubSum($array, $center + 1, $right);
            // 计算包含center的最大值，判断是情况1，2，3
            $s1 = 0;
            $lefts = 0;
            for ($i = $center; $i >= $left; $i--) {
                $lefts = $lefts + $array[$i];
                if ($lefts > $s1) {
                    $s1 = $lefts;
                }
            }
            $s2 = 0;
            $rights = 0;
            for ($i = $center + 1; $i <= $right; $i++) {
                $rights = $rights + $array[$i];
                if ($rights > $s2) {
                    $s2 = $rights;
                }
            }
            $sum = $s1 + $s2;
            // 情况1
            if ($sum < $leftSum) {
                $sum = $leftSum;
            }
            // 情况2
            if ($sum < $rightSum) {
                $sum = $rightSum;
            }
        }
        return $sum;
    }

    /**
     * 求和
     * 输入参数n,可以求到1+2+3+...+n的和
     * @param $n
     * @return int
     */
    public function sumRecursive($n): int
    {
        if ($n > 1) {
            return $n + $this->sumRecursive($n - 1);
        } else {
            return 1;
        }
    }

    /**
     * 递归实现迪卡尔乘积
     * @param $arr array 操作的数组
     * @param array $tmp
     * @return array
     */
    public function descarteRecursive($arr, $tmp = array())
    {
        static $n_arr = array();
        foreach (array_shift($arr) as $v) {
            $tmp[] = $v;
            if ($arr) {
                $this->descarteRecursive($arr, $tmp);
            } else {
                $n_arr[] = $tmp;
            }
            array_pop($tmp);
        }
        return $n_arr;
    }

    /**
     * 阶乘函数
     *
     */
    public function factorialRecursive(int $num)
    {
        // 边界条件：1, n=0
        if ($num == 0) {
            return 1;
        }
        // 递归体：n(n-1)!,n>0
        if ($num > 0) {
            return $num * $this->factorialRecursive($num - 1);
        }
        return false;
    }

    /**
     * 斐波那契数列（Fibonacci Sequence）又称黄金分割数列 兔子数列
     * 指的是这样一个数列：1、1、2、3、5、8、13、21
     * @param $n
     * @return mixed
     */
    public function fibonacciRecursive($n)
    {
        // F0=0，F1=1
        if ($n <= 1) {
            return $n;
        }
        // Fn=F(n-1)+F(n-2)（n>=2，n∈N*）
        return $this->fibonacciRecursive($n - 1) + $this->fibonacciRecursive($n - 2);
    }

    /**
     * 牛年求牛
     * 有一母牛，到4岁可生育，每年一头，所生均是一样的母牛,15岁绝育，不再能生，20岁死亡，问n年后有多少头牛。
     * @param int $n 年
     * @return int
     */
    public function cattleRecursive(int $n): int
    {
        static $num = 1;
        for ($i = 1; $i <= $n; $i++) {
            if ($i == 20) {
                $num--; //死亡需减一
            } else if ($i >= 4 && $i < 15) {
                $num++; //生小母牛（这里有小母牛）
                $this->cattleRecursive($n - $i); //小母牛生小母牛（这里不包含小母牛）
            }
        }
        return $num;
    }

    /**
     * 用递归打印当前目前下的所有文件,目录及子目录....
     * $path 目录
     * $lev 层级 进入一层,目录更深,明显显示出来
     */
    public function showDir($path, $lev = 0)
    {
        $fh = opendir($path);
        while ($row = readdir($fh)) {
            //如果目录为.和..就跳过
            if (($row == '.') || ($row == '..')) {
                continue;
            }
            //如果目录里还有目录,继续往下读取目录
            if (is_dir($path . '/' . $row)) {
                $this->showdir($path . '/' . $row, $lev + 1);
            }
        }
        closedir($fh);
    }

    /**
     * 汉诺塔游戏
     * 1.有三根杆子A,B,C。A杆上有若干碟子
     * 2.每次移动一块碟子,小的只能叠在大的上面
     * 3.把所有碟子从A杆全部移到C杆上
     * 经过研究发现，汉诺塔的破解很简单，就是按照移动规则向一个方向移动金片：
     * 如3阶汉诺塔的移动：A→C,A→B,C→B,A→C,B→A,B→C,A→C
     * @param int $n
     * @param string $x
     * @param string $y
     * @param string $z
     */
    function hanoiGames(int $n, string $x, string $y, string $z)
    {
        if ($n == 1) {
            echo 'move disk 1 from ' . $x . ' to ' . $z . "\n";
        } else {
            $this->hanoiGames($n - 1, $x, $z, $y);
            echo 'move disk ' . $n . ' from ' . $x . ' to ' . $z . "\n";
            $this->hanoiGames($n - 1, $y, $x, $z);
        }
    }

    /**
     * 非递归方式
     *
     * @param $n
     * @return mixed
     */
    public function fibonacci($n)
    {
        if ($n <= 1) {
            return $n;
        }
        for ($fib = [0, 1], $i = 2; $i <= $n; $i++) {
            $fib[$i] = $fib[$i - 1] + $fib[$i - 2];
        }
        return $fib[$n];
    }

    /**
     * 有5个人偷了一堆苹果，准备在第二天分赃。
     * 晚上，有一人遛出来，把所有苹果分成5份，但是多了一个，顺手把这个扔给树上的猴了，自己先拿1/5藏了。
     * 没想到其他四人也都是这么想的，都如第一个人一样分成5份把多的那一个扔给了猴，偷走了1/5。
     * 第二天，大家分赃，也是分成5份多一个扔给猴了。最后一人分了一份。
     * 问：共有多少苹果？N 个人呢？
     * @param int $n N个人
     * @return int $r 共有多少苹果
     */
    function stealingApples(int $n): int
    {
        for ($r = 1; ; $r++) {
            $t = $r;
            for ($i = 0; $i <= $n; $i++) {
                if ($t % $n == 1) {
                    $t = $t - round($t / $n) - 1;
                } else {
                    continue 2;
                }
            }
            return $r;
        }
    }
}